﻿using System.Collections.Generic;
using System;
using Unity.Collections;

namespace GameBasic
{

    public static class ExtCollection
    {
        #region List

        public static bool IsLegalIndex<T>(this List<T> list, int index)
        {
            return index >= 0 && index < list.Count;
        }

        public static bool IsNullOrEmpty<T>(this List<T> list)
        {
            return list == null || list.Count == 0;
        }

        public static Dictionary<K, V> ToDictionary<K, V>(this List<V> list, Func<V, K> keyGetter)
        {
            Dictionary<K, V> result = new Dictionary<K, V>(list.Count);
            for (int i = 0, length = list.Count; i < length; i++)
            {
                V item = list[i];
                result[keyGetter(item)] = item;
            }

            return result;
        }

        public static void EnsureCapacity<T>(this List<T> list, int capacity)
        {
            if (list.Capacity < capacity)
                list.Capacity = capacity;
            /*
            if (list.Capacity >= capacity)
                return list;
            if (list.Count == 0)
                return new List<T>(capacity);

            List<T> result = new List<T>(capacity);
            result.AddRange(list);
            return result;
            */
        }

        public static void ForEach<T>(this List<T> list, Action<int, T> act)
        {
            int length = list.Count;
            for (int i = 0; i < length; i++)
                act(i, list[i]);
        }
        #endregion

        #region BinarySearch
        /// <summary>
        /// Find item or insert position, Faster than <see cref="IList{T}.BinarySearch(T)"/>.
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">Target list</param>
        /// <param name="item">Item need to find</param>
        /// <param name="i">Index of the item or insert index</param>
        /// <returns>true if found</returns>
        public static bool BinarySearch<T>(this IList<T> list, in T item, out int i) where T : IComparable<T>
        {
            return BinarySearch(list, item, out i, new CompareStruct<T, T>());
        }

        /// <summary>
        /// Search T by K, return true if found; ind contains item and index, if not found, ind.index is the insert position
        /// </summary>
        public static bool BinarySearch<T, K, C>(this IList<T> list, K key, out Idx<T> idx, in C comparer) where T : struct where C : IKeyComparer<K, T>
        {
            bool found = BinarySearch(list, key, out int i, comparer);
            if (found)
                idx.value = list[i];
            else
                idx = default;
            idx.index = i;

            return found;
        }

        public static bool BinarySearch<T, K, C>(this IList<T> list, K key, out int i, in C comparer) where C : IKeyComparer<K, T>
        {
            // Result
            i = 0;

            // Empty
            int length = list.Count;
            if (length == 0)
                return false;

            // Search
            bool found = false;
            int left = 0;
            int right = length - 1;

            while (true)
            {
                if (left < right)
                {
                    // (left + right) / 2
                    i = (left + right) >> 1;

                    int compare = comparer.CompareStruct(key, list[i]);
                    found = compare == 0;

                    if (found)
                        break;
                    else if (compare < 0)
                        right = i - 1;
                    else
                        left = i + 1;
                }
                else
                {
                    i = left;

                    int compare = comparer.CompareStruct(key, list[i]);
                    found = compare == 0;
                    if (compare > 0)
                        i++;

                    break;
                }
            }

            return found;
        }

        public static bool BinarySearch<T>(this NativeArray<T> array, in T item, out int i) where T : struct, IComparable<T>
        {
            return BinarySearch(array, item, out i, new CompareStruct<T, T>());
        }

        /// <summary>
        /// Search index <paramref name="i"/> by <paramref name="key"/>, return true if found; if not found
        /// </summary>
        public static bool BinarySearch<T, K, C>(this NativeArray<T> array, K key, out int i, in C comparer) where T : struct where C : IKeyComparer<K, T>
        {
            // Result
            i = 0;

            // Empty
            int length = array.Length;
            if (length == 0)
                return false;

            // Search
            bool found = false;
            int left = 0;
            int right = length - 1;

            while (true)
            {
                if (left < right)
                {
                    // (left + right) / 2
                    i = (left + right) >> 1;

                    int compare = comparer.CompareStruct(key, array[i]);
                    found = compare == 0;

                    if (found)
                        break;
                    else if (compare < 0)
                        right = i - 1;
                    else
                        left = i + 1;
                }
                else
                {
                    i = left;

                    int compare = comparer.CompareStruct(key, array[i]);
                    found = compare == 0;
                    if (compare > 0)
                        i++;

                    break;
                }
            }

            return found;
        }

        /// <summary>
        /// Search T by K, return true if found; ind contains item and index, if not found, ind.index is the insert position
        /// </summary>
        public static bool BinarySearch<T, K, C>(this NativeArray<T> array, K key, out Idx<T> idx, in C comparer) where T : struct where C : IKeyComparer<K, T>
        {
            bool found = BinarySearch(array, key, out int i, comparer);
            if (found)
                idx.value = array[i];
            else
                idx = default;
            idx.index = i;

            return found;
        }

        public static bool BinarySearch<T, K, C>(this NativeArray<T> array, K key, out T result, in C comparer) where T : struct, IIndexed<T> where C : IKeyComparer<K, T>
        {
            bool found = BinarySearch(array, key, out int i, comparer);
            if (found)
                result = array[i];
            else
                result = default;
            result.Index = i;

            return found;
        }

        /*
        public static void BinarySearchBenchMark()
        {
            int length = 128;
            BenchMark(length);
            BenchMark2(length);
        }

        static void BenchMark(int length)
        {
            List<int> rng = new List<int>(length);
            List<int> list = new List<int>(length);
            Dictionary<int, int> dic = new Dictionary<int, int>(length);
            for (int i = 0; i < length; i++)
            {
                rng.Add(UnityEngine.Random.Range(0, 256));
                //list[i] = i;
                list.Add(i);
                dic.Add(i, i);
            }

            var stopWatch = new System.Diagnostics.Stopwatch();
            long time0 = 0;
            long time1 = 0;
            int loopCount = 10;

            stopWatch.Start();
            for (int i = 0; i < loopCount; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    int r = rng[j];
                    list.BinarySearch(r, out int v);
                }
            }
            stopWatch.Stop();
            time0 = stopWatch.ElapsedTicks;

            stopWatch.Restart();
            for (int i = 0; i < loopCount; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    int r = rng[j];
                    dic.TryGetValue(r, out int v);
                }
            }
            stopWatch.Stop();
            time1 = stopWatch.ElapsedTicks;

            Debug.Log(time0 + ", " + time1);
        }

        static void BenchMark2(int length)
        {
            NativeArray<int> rng = new NativeArray<int>(length, Allocator.Persistent);
            NativeArray<int> list = new NativeArray<int>(length, Allocator.Persistent);
            NativeHashMap<int, int> dic = new NativeHashMap<int, int>(length, Allocator.Persistent);
            for (int i = 0; i < length; i++)
            {
                rng[i] = UnityEngine.Random.Range(0, 256);
                list[i] = i;
                dic.Add(i, i);
            }

            var stopWatch = new System.Diagnostics.Stopwatch();
            long time0 = 0;
            long time1 = 0;
            int loopCount = 10;

            stopWatch.Start();
            for (int i = 0; i < loopCount; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    int r = rng[j];
                    list.BinarySearch(r, out int v);
                }
            }
            stopWatch.Stop();
            time0 = stopWatch.ElapsedTicks;

            stopWatch.Restart();
            for (int i = 0; i < loopCount; i++)
            {
                for (int j = 0; j < length; j++)
                {
                    int r = rng[j];
                    dic.TryGetValue(r, out int v);
                }
            }
            stopWatch.Stop();
            time1 = stopWatch.ElapsedTicks;

            Debug.Log(time0 + ", " + time1);

            rng.Dispose();
            list.Dispose();
            dic.Dispose();
        }
        */
        #endregion

        #region Dictionary
        public static void AddAll<K, V>(this Dictionary<K, V> dic, List<V> values, Func<V, K> keyGetter)
        {
            int length = values.Count;
            for (int i = 0; i < length; i++)
                dic.Add(keyGetter(values[i]), values[i]);
        }

        public static void AddAll<K, V>(this Dictionary<K, V> dic, V[] values, Func<V, K> keyGetter)
        {
            for (int i = 0; i < values.Length; i++)
                dic.Add(keyGetter(values[i]), values[i]);
        }

        public static void SetAll<K, V>(this Dictionary<K, V> dic, V[] values, Func<V, K> keyGetter)
        {
            for (int i = 0; i < values.Length; i++)
                dic[keyGetter(values[i])] = values[i];
        }
        #endregion
    }
}